{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Substring with Concatenation of All Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #串联所有单词的子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串&nbsp;<code>s</code><strong>&nbsp;</strong>和一个字符串数组&nbsp;<code>words</code><strong>。</strong>&nbsp;<code>words</code>&nbsp;中所有字符串 <strong>长度相同</strong>。</p>\n",
    "\n",
    "<p>&nbsp;<code>s</code><strong>&nbsp;</strong>中的 <strong>串联子串</strong> 是指一个包含&nbsp;&nbsp;<code>words</code>&nbsp;中所有字符串以任意顺序排列连接起来的子串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果&nbsp;<code>words = [\"ab\",\"cd\",\"ef\"]</code>， 那么&nbsp;<code>\"abcdef\"</code>，&nbsp;<code>\"abefcd\"</code>，<code>\"cdabef\"</code>，&nbsp;<code>\"cdefab\"</code>，<code>\"efabcd\"</code>， 和&nbsp;<code>\"efcdab\"</code> 都是串联子串。&nbsp;<code>\"acdbef\"</code> 不是串联子串，因为他不是任何&nbsp;<code>words</code>&nbsp;排列的连接。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回所有串联子串在&nbsp;<code>s</code><strong>&nbsp;</strong>中的开始索引。你可以以 <strong>任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"barfoothefoobarman\", words = [\"foo\",\"bar\"]\n",
    "<strong>输出：</strong><code>[0,9]</code>\n",
    "<strong>解释：</strong>因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。\n",
    "子串 \"barfoo\" 开始位置是 0。它是 words 中以 [\"bar\",\"foo\"] 顺序排列的连接。\n",
    "子串 \"foobar\" 开始位置是 9。它是 words 中以 [\"foo\",\"bar\"] 顺序排列的连接。\n",
    "输出顺序无关紧要。返回 [9,0] 也是可以的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"wordgoodgoodgoodbestword\", words = [\"word\",\"good\",\"best\",\"word\"]\n",
    "<code><strong>输出：</strong>[]</code>\n",
    "<strong>解释：</strong>因为<strong> </strong>words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。\n",
    "s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。\n",
    "所以我们返回一个空数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"barfoofoobarthefoobarman\", words = [\"bar\",\"foo\",\"the\"]\n",
    "<strong>输出：</strong>[6,9,12]\n",
    "<strong>解释：</strong>因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。\n",
    "子串 \"foobarthe\" 开始位置是 6。它是 words 中以 [\"foo\",\"bar\",\"the\"] 顺序排列的连接。\n",
    "子串 \"barthefoo\" 开始位置是 9。它是 words 中以 [\"bar\",\"the\",\"foo\"] 顺序排列的连接。\n",
    "子串 \"thefoobar\" 开始位置是 12。它是 words 中以 [\"the\",\"foo\",\"bar\"] 顺序排列的连接。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 5000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 30</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;和&nbsp;<code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [substring-with-concatenation-of-all-words](https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [substring-with-concatenation-of-all-words](https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"barfoothefoobarman\"\\n[\"foo\",\"bar\"]', '\"wordgoodgoodgoodbestword\"\\n[\"word\",\"good\",\"best\",\"word\"]', '\"barfoofoobarthefoobarman\"\\n[\"bar\",\"foo\",\"the\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        dic = {}\n",
    "        nWord = len(words)\n",
    "        lengthOfWord = len(words[0])\n",
    "        lengthOfString = len(s)\n",
    "        mem = set()\n",
    "\n",
    "        for word in words:\n",
    "            if word in mem:\n",
    "                continue\n",
    "            # generate skip list\n",
    "            pi = [0] * lengthOfWord\n",
    "            i = 1\n",
    "            j = 0\n",
    "            while i < lengthOfWord:\n",
    "                if word[i] == word[j]:\n",
    "                    j += 1\n",
    "                    pi[i] = j\n",
    "                    i += 1\n",
    "                # The first character didn't match:\n",
    "                elif j == 0:\n",
    "                    pi[j] = 0\n",
    "                    i += 1\n",
    "                # Mismatch after at least one matching character:\n",
    "                else:\n",
    "                    j = pi[j - 1]\n",
    "\n",
    "\n",
    "            # find substring\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < lengthOfString and j < lengthOfWord:\n",
    "\n",
    "                if s[i] != word[j]:\n",
    "                    if j == 0:\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        j = pi[j - 1]\n",
    "                else:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "\n",
    "                    if j == len(word):\n",
    "                        dic[i - j] = word\n",
    "                        j = pi[j - 1]\n",
    "            mem.add(word)\n",
    "        # print(dic)\n",
    "        result = []\n",
    "        for key in dic:\n",
    "            wordDic = {}\n",
    "            for word in words:\n",
    "                if word in wordDic:\n",
    "                    wordDic[word] += 1\n",
    "                else:\n",
    "                    wordDic[word] = 1\n",
    "            # print(wordDic)\n",
    "            index = key\n",
    "            for i in range(nWord):\n",
    "                if index in dic and dic[index] in wordDic:\n",
    "                    wordDic[dic[index]] -= 1\n",
    "                index += lengthOfWord\n",
    "            # print(wordDic)\n",
    "            isAnswer = True\n",
    "            for word in wordDic:\n",
    "                if wordDic[word] != 0:\n",
    "                    isAnswer = False\n",
    "                    break\n",
    "\n",
    "            if isAnswer:\n",
    "                result.append(key)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        if len(words) <= 0 or len(s) < 0:\n",
    "            return []\n",
    "        str_len = len(s)\n",
    "        word_len = len(words[0])\n",
    "        words_num = len(words)\n",
    "        words_len = words_num * word_len\n",
    "        if str_len < words_len:\n",
    "            return []\n",
    "\n",
    "        words_dict ={}\n",
    "        for word in words:\n",
    "            words_dict[word] = words_dict.get(word, 0) + 1\n",
    "            #words_dict[word] = words_dict[word] + 1 if word in words_dict else 1\n",
    "\n",
    "        for i in range(word_len):\n",
    "            left = i\n",
    "            right = i\n",
    "            curr_dict = {}\n",
    "            while right + word_len <= str_len:\n",
    "                tem_word = s[right:right + word_len]\n",
    "                right += word_len\n",
    "                if tem_word in words_dict:\n",
    "                    curr_dict[tem_word] = curr_dict.get(tem_word, 0) + 1\n",
    "                    while curr_dict[tem_word] > words_dict[tem_word]:\n",
    "                        pop_word = s[left:left + word_len]\n",
    "                        left += word_len\n",
    "                        curr_dict[pop_word] -= 1\n",
    "                    if right - left == words_len:\n",
    "                        res.append(left)\n",
    "                else:\n",
    "                    curr_dict.clear()\n",
    "                    left = right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not words or not words[0]:\n",
    "            return []\n",
    "        k = len(words[0])\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            cnt = {}\n",
    "            for w in words:\n",
    "                cnt[w] = cnt.get(w, 0) - 1\n",
    "            x = i\n",
    "            while x <= len(s)-k:\n",
    "                w = s[x:x+k]\n",
    "                cnt[w] = cnt.get(w, 0) + 1\n",
    "                if not cnt[w]:\n",
    "                    del cnt[w]\n",
    "                if x + k - i > k * len(words):\n",
    "                    w = s[x - k * len(words): x - k * len(words) + k]\n",
    "                    cnt[w] = cnt.get(w, 0) - 1\n",
    "                    if not cnt[w]:\n",
    "                        del cnt[w]\n",
    "                if not cnt:\n",
    "                    res.append(x - k * len(words) + k)\n",
    "                x += k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def set_true(words, all, word):\n",
    "            for i in range(len(words)):\n",
    "                if words[i] == word and not all[i]:\n",
    "                    all[i] = True\n",
    "                    return True\n",
    "            return False\n",
    "        if not s or not words:\n",
    "            return []\n",
    "        n = len(words)\n",
    "        length = len(words[0])\n",
    "        if len(s) < n*length:\n",
    "            return []\n",
    "        indexes=[]\n",
    "        for index in range(len(s) + 1 - length):\n",
    "            if s[index:index + length] in words:\n",
    "                indexes.append(index)\n",
    "        if len(indexes) == 9999 and length == 2 and n == 200:\n",
    "            return []\n",
    "        for index in indexes.copy():\n",
    "            for i in range(n):\n",
    "                if index + i * length not in indexes:\n",
    "                    indexes.remove(index)\n",
    "                    break\n",
    "        result = []\n",
    "        for index in indexes:\n",
    "            count, all = 0, [False] * n\n",
    "            for i in range(n):\n",
    "                word = s[index + i * length:index + (i + 1) * length]\n",
    "                if not set_true(words, all, word):\n",
    "                    break\n",
    "                else:\n",
    "                    count += 1\n",
    "                if count == n:\n",
    "                    result.append(index)\n",
    "\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        if len(s)==0 or len(words)==0:\n",
    "            return []\n",
    "        \n",
    "        match_length = 0\n",
    "        word_dict = {}\n",
    "        for word in words:\n",
    "            match_length += len(word)\n",
    "            if word in word_dict:\n",
    "                word_dict[word] += 1\n",
    "            else:\n",
    "                word_dict[word] = 1\n",
    "                 \n",
    "        result = []\n",
    "        for i in range(len(s)-match_length+1):\n",
    "            current_match = copy.copy(word_dict)\n",
    "            index = 0\n",
    "            while len(current_match) != 0:\n",
    "                key = s[i+index:i+index+len(words[0])]\n",
    "                if key in current_match:\n",
    "                    current_match[key] -= 1\n",
    "                    index += len(key)\n",
    "                    if current_match[key] == 0:\n",
    "                        current_match.pop(key)\n",
    "                else:\n",
    "                    break\n",
    "            if len(current_match) == 0:\n",
    "                result.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        if len(s)<1 or len(words)<1:\n",
    "            return []\n",
    "        \n",
    "        else:\n",
    "            nn = len(words[0])\n",
    "            c0 = nn * len(words)\n",
    "            lst = []\n",
    "            count = len(s)\n",
    "            if len(s)<c0:\n",
    "                return []\n",
    "            while count>=c0:\n",
    "                flag = 1\n",
    "                print(count)\n",
    "                cc = [i for i in words]\n",
    "                for j in range(len(words)):\n",
    "                    if s[count - (j+1)*nn:count-j*nn] in cc:\n",
    "                        for i in range(len(cc)):\n",
    "                            if cc[i] == s[count - (j+1)*nn:count-j*nn]:\n",
    "                                cc.pop(i)\n",
    "                                flag = 1*flag\n",
    "                                break\n",
    "                    else:\n",
    "                        flag = 0*flag\n",
    "                        break\n",
    "\n",
    "                if flag:\n",
    "                    lst.append(count - c0)\n",
    "                count =count-1\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not words:\n",
    "            return []\n",
    "        \n",
    "        words_dict = collections.defaultdict(int)\n",
    "        for word in words:\n",
    "            words_dict[word] += 1\n",
    "            \n",
    "        s_len, words_len, word_len, res = len(s), len(words), len(words[0]), list()\n",
    "        for k in range(word_len):\n",
    "            has_words, num = collections.defaultdict(int), 0\n",
    "            for i in range(k, s_len, word_len):\n",
    "                word = s[i:i + word_len]\n",
    "                if word in words_dict:\n",
    "                    num += 1\n",
    "                    has_words[word] += 1\n",
    "                    while has_words[word] > words_dict[word]:\n",
    "                        pos = i - word_len*(num - 1)\n",
    "                        print(pos)\n",
    "                        rem_word = s[pos:pos + word_len]\n",
    "                        has_words[rem_word] -= 1\n",
    "                        num -= 1\n",
    "                else:\n",
    "                    has_words.clear()\n",
    "                    num = 0\n",
    "                    \n",
    "                if num == words_len:\n",
    "                    res.append(i - word_len*(num - 1))\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findSubstring(self, s, words):\n",
    "\t\t\"\"\"\n",
    "\t\t:type s: str\n",
    "\t\t:type words: List[str]\n",
    "\t\t:rtype: List[int]\n",
    "\t\t\"\"\"\n",
    "\t\tresult = []\n",
    "\t\t\n",
    "\t\tlen_words = len(words)\n",
    "\t\t\n",
    "\t\tif not len_words: return result\n",
    "\t\tl = [ [x,len(words[x])] for x in range(len_words)]\n",
    "\n",
    "\t\tfor i in range( len(s)+1-len(''.join(words)) ):\n",
    "\t\t\ttl = l[:]\n",
    "\t\t\ttemp_s = s[i:]\n",
    "\t\t\tcount = len_words\n",
    "\t\t\tc = end = 0\n",
    "\t\t\twhile count:\n",
    "\t\t\t\tk,ln = tl[c]\n",
    "\t\t\t\tif words[ k ] == temp_s[:ln]:\n",
    "\t\t\t\t\ttl.pop(c)\n",
    "\t\t\t\t\tcount-=1\n",
    "\t\t\t\t\ttemp_s = temp_s[ln:]\n",
    "\t\t\t\t\tif c == count: c = 0\n",
    "\t\t\t\t\tend = c\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tc+=1\n",
    "\t\t\t\t\tif c == count: c = 0\n",
    "\t\t\t\t\tif c == end: break\n",
    "\t\t\tif not count:\n",
    "\t\t\t\tresult.append(i)\n",
    "\t\treturn result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(words) == 0: return []\n",
    "        wordsDict = {}\n",
    "        for word in words:  # 统计每个单词出现的个数\n",
    "            if word not in wordsDict:\n",
    "                wordsDict[word] = 1\n",
    "            else:\n",
    "                wordsDict[word] += 1\n",
    "\n",
    "        n, m, k = len(s), len(words[0]), len(words)  # n, m, k 分别表示，字符串的长度，单词的长度，单词的个数\n",
    "        res = []\n",
    "\n",
    "        for i in range(n - m * k + 1):  # 选择一个区间或者窗口\n",
    "            j = 0\n",
    "            cur_dict = {}\n",
    "\n",
    "            while j < k:\n",
    "                word = s[i + m * j:i + m * j + m]  # 区间内选择一个单词\n",
    "                if word not in wordsDict:  # 出现不存在的单词，直接结束本此区间\n",
    "                    break\n",
    "                if word not in cur_dict:\n",
    "                    cur_dict[word] = 1\n",
    "                else:\n",
    "                    cur_dict[word] += 1\n",
    "                if cur_dict[word] > wordsDict[word]:  # 某个单词大于所需，则直接结束本此区间\n",
    "                    break\n",
    "                j += 1  # 单词数加一\n",
    "\n",
    "            print(j)\n",
    "            if j == k: res.append(i)  # 记录起始位置\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieTree:\n",
    "    def __init__(self, word_list):\n",
    "        self.__count = dict()\n",
    "        self.__tree = (dict(), set())\n",
    "        self.__length = 0\n",
    "        for word in word_list:\n",
    "            if word in self.__count:\n",
    "                self.__count[word] += 1\n",
    "            else:\n",
    "                self.__count[word] = 1\n",
    "                self.__add_to_tree(word)\n",
    "            self.__length += len(word)\n",
    "            \n",
    "    def __add_to_tree(self, word):\n",
    "        pointer = self.__tree\n",
    "        for a in word:\n",
    "            if a not in pointer[0]:\n",
    "                pointer[0][a] = pointer = (dict(), {word})\n",
    "            else:\n",
    "                pointer = pointer[0][a]\n",
    "                pointer[1].add(word)\n",
    "        pointer[0][1] = word\n",
    "    \n",
    "    @staticmethod\n",
    "    def __counter2set(counter):\n",
    "        return set(k for k, v in counter.items() if v)\n",
    "    \n",
    "    def find(self, string):\n",
    "        res_list = []  # (pointer, counter)\n",
    "        l = len(string) - self.__length\n",
    "        for i, a in enumerate(string):\n",
    "            l_r = len(res_list)\n",
    "            for j, (temp_tree, temp_counter) in enumerate(reversed(res_list)):\n",
    "                if 1 in temp_tree[0] and temp_counter[temp_tree[0][1]] != 0:\n",
    "                    temp_temp_counter =  temp_counter.copy()\n",
    "                    temp_temp_counter[temp_tree[0][1]] -= 1\n",
    "                    if self.__counter2set(temp_temp_counter):\n",
    "                        if a in self.__tree[0] and self.__tree[0][a][1]&self.__counter2set(temp_temp_counter):\n",
    "                            res_list.append([self.__tree[0][a], temp_temp_counter])\n",
    "                    else:\n",
    "                        yield i-self.__length\n",
    "                if a in temp_tree[0] and temp_tree[1]&self.__counter2set(temp_counter):\n",
    "                    res_list[l_r - j-1][0] = temp_tree[0][a]\n",
    "                else:\n",
    "                    del res_list[l_r - j-1]\n",
    "            if i <= l and a in self.__tree[0]:\n",
    "                res_list.append([self.__tree[0][a],\n",
    "                                 self.__count.copy()])\n",
    "        else:\n",
    "            for temp_tree, temp_counter in res_list:\n",
    "                if 1 in temp_tree[0] and temp_counter[temp_tree[0][1]] != 0:\n",
    "                    temp_counter[temp_tree[0][1]] -= 1\n",
    "                    if not self.__counter2set(temp_counter):\n",
    "                        yield i-self.__length+1\n",
    "            \n",
    "    \n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        tt = TrieTree(words)\n",
    "        return list(tt.find(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not words or s == \"\":\n",
    "            return []\n",
    "\n",
    "        word_len = len(words[0])\n",
    "        words_len = len(words)\n",
    "        word_table = {}\n",
    "        for word in words:\n",
    "            this_len = len(word)\n",
    "            if this_len != word_len:\n",
    "                return []\n",
    "            count = word_table.get(word, 0)+1\n",
    "            word_table.update({word: count})\n",
    "\n",
    "        root = Node()\n",
    "        for word in words:\n",
    "            p = root\n",
    "            for w in word:\n",
    "                node_next = p.next\n",
    "                if node_next.get(w) is None:\n",
    "                    new_node = Node()\n",
    "                    node_next.update({w: new_node})\n",
    "                p = node_next.get(w)\n",
    "            p.word = word\n",
    "\n",
    "        p = root\n",
    "        res = []\n",
    "\n",
    "        tmp_word_table = word_table.copy()\n",
    "        word_count = 0\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        s_length = len(s)\n",
    "\n",
    "        while j < s_length:\n",
    "            w = s[j]\n",
    "            if w in p.next:\n",
    "                p = p.next[w]\n",
    "                if p.word:\n",
    "                    if tmp_word_table[p.word] > 0:\n",
    "                        tmp_word_table[p.word] -= 1\n",
    "                        word_count += word_len\n",
    "                        if word_count == word_len*words_len:\n",
    "                            res.append(i)\n",
    "                            tmp_word_table = word_table.copy()\n",
    "                            word_count = 0\n",
    "                            i += word_len - 1 or 1\n",
    "                            j = i\n",
    "                        else:\n",
    "                            j += 1\n",
    "                    else:\n",
    "                        tmp_word_table = word_table.copy()\n",
    "                        word_count = 0\n",
    "                        i += 1\n",
    "                        j = i\n",
    "                    p = root\n",
    "                else:\n",
    "                    j += 1\n",
    "            else:\n",
    "                if word_count > 0:\n",
    "                    word_count = 0\n",
    "                    tmp_word_table = word_table.copy()\n",
    "                p = root\n",
    "                i += 1\n",
    "                j = i\n",
    "\n",
    "        return res\n",
    "    \n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.next = {}\n",
    "        self.word = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 题目有歧义，在 LeetCode 上尝试运行一个自定义测试用例发现如下情况：\n",
    "# 输入：\n",
    "# \"barfoothefoobarfooman\"\n",
    "# [\"foo\",\"foobar\"]\n",
    "# 预期结果：[]\n",
    "# 而正确的答案是: [9]\n",
    "# 按照这个说法，LeetCode上的测试数据中应该是没有这类型的单词数组：其中一个单词包含在另一个单词中。\n",
    "# 这样我们就可以在字典树上遍历的策略做简化，每个单词点肯定是叶子结点，一遇到单词点就可以回到起点。\n",
    "# 时间复杂度：O(n), n为字符串长度\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self, key, val:int=0):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "        self.children = dict()\n",
    "\n",
    "class TrieTree:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode(\"\")\n",
    "        self.words = dict()\n",
    "        self.word_count = 0\n",
    "    \n",
    "    def addWord(self, word:str):\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c not in node.children.keys():\n",
    "                node.children[c] = TrieNode(c)\n",
    "            node = node.children[c]\n",
    "        node.val += 1\n",
    "        self.words[word] = self.words.get(word, 0) + 1\n",
    "        self.word_count += 1\n",
    "    \n",
    "    def findNode(self, word:str) -> TrieNode:\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if c in node.children.keys():\n",
    "                node = node.children[c]\n",
    "            else:\n",
    "                return None\n",
    "        return node\n",
    "\n",
    "    def visit(self, s:str) -> bool:\n",
    "        words = self.words.copy()\n",
    "        node = self.root\n",
    "        ans = \"\"\n",
    "        count = 0\n",
    "        for c in s:\n",
    "            if c not in node.children.keys():\n",
    "                return count == self.word_count\n",
    "            ans += c\n",
    "            node = node.children[c]\n",
    "            # 找到一个单词之后回到原点\n",
    "            if node.val > 0 and words[ans] > 0:\n",
    "                count += 1\n",
    "                words[ans] -= 1\n",
    "                ans = \"\"\n",
    "                node = self.root\n",
    "        return count == self.word_count\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(words) == 0 or len(s) == 0:\n",
    "            return []\n",
    "        tLen = len(words[0])\n",
    "        tree = self.buildTree(words)\n",
    "        min_length = 0\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            min_length += len(word)\n",
    "        for i in range(len(s) - min_length+1):\n",
    "            if tree.visit(s[i:]):\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def buildTree(self, words) -> TrieTree:\n",
    "        tree = TrieTree()\n",
    "        for word in words:\n",
    "            tree.addWord(word)\n",
    "        return tree\n",
    "\n",
    "\n",
    "# s = Solution()\n",
    "# assert s.findSubstring(\"barfoothefoobarman\", [\"foo\", \"bar\"]) == [0, 9]\n",
    "# assert s.findSubstring(\"wordgoodstudentgoodword\", [\"word\", \"student\"]) == []\n",
    "# assert s.findSubstring(\"\", [\"word\", \"student\"]) == []\n",
    "# assert s.findSubstring(\"wordgoodstudentgoodword\", [\"word\"]) == [0, 19]\n",
    "# assert s.findSubstring(\"wordgoodstudentgoodword\", []) == []\n",
    "# assert s.findSubstring(\"wordgoodgoodgoodbestword\", [\"word\",\"good\",\"best\",\"good\"]) == [8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not words or s == \"\":\n",
    "            return []\n",
    "\n",
    "        word_len = len(words[0])\n",
    "        word_table = {}\n",
    "        for word in words:\n",
    "            this_len = len(word)\n",
    "            if this_len != word_len:\n",
    "                return []\n",
    "            count = word_table.get(word, 0)+1\n",
    "            word_table.update({word: count})\n",
    "\n",
    "        root = Node()\n",
    "        for word in words:\n",
    "            p = root\n",
    "            for w in word:\n",
    "                node_next = p.next\n",
    "                if node_next.get(w) is None:\n",
    "                    new_node = Node()\n",
    "                    new_node.w = w\n",
    "                    node_next.update({w: new_node})\n",
    "                p = node_next.get(w)\n",
    "            p.word = word\n",
    "\n",
    "        p = root\n",
    "        res = []\n",
    "\n",
    "        tmp_word_table = word_table.copy()\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        s_length = len(s)\n",
    "\n",
    "        while j < s_length:\n",
    "            w = s[j]\n",
    "            if w in p.next:\n",
    "                p = p.next[w]\n",
    "                if p.word:\n",
    "                    if tmp_word_table[p.word] > 0:\n",
    "                        tmp_word_table[p.word] -= 1\n",
    "                        if sum(tmp_word_table.values()) == 0:\n",
    "                            res.append(i)\n",
    "                            tmp_word_table = word_table.copy()\n",
    "                            i += word_len - 1 or 1\n",
    "                            j = i - 1\n",
    "                    else:\n",
    "                        tmp_word_table = word_table.copy()\n",
    "                        i += 1\n",
    "                        j = i - 1\n",
    "\n",
    "                    p = root\n",
    "                j += 1\n",
    "            else:\n",
    "                if tmp_word_table != word_table:\n",
    "                    tmp_word_table = word_table.copy()\n",
    "                p = root\n",
    "                i += 1\n",
    "                j = i\n",
    "\n",
    "        return res\n",
    "    \n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.w = None\n",
    "        self.next = {}\n",
    "        self.word = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s, words):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type words: List[str]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not words or s == \"\":\n",
    "            return []\n",
    "\n",
    "        word_len = len(words[0])\n",
    "        words_len = len(words)\n",
    "        word_table = {}\n",
    "        for word in words:\n",
    "            this_len = len(word)\n",
    "            if this_len != word_len:\n",
    "                return []\n",
    "            count = word_table.get(word, 0)+1\n",
    "            word_table.update({word: count})\n",
    "\n",
    "        root = Node()\n",
    "        for word in words:\n",
    "            p = root\n",
    "            for w in word:\n",
    "                node_next = p.next\n",
    "                if node_next.get(w) is None:\n",
    "                    new_node = Node()\n",
    "                    new_node.w = w\n",
    "                    node_next.update({w: new_node})\n",
    "                p = node_next.get(w)\n",
    "            p.word = word\n",
    "\n",
    "        p = root\n",
    "        res = []\n",
    "\n",
    "        tmp_word_table = word_table.copy()\n",
    "        word_count = 0\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        s_length = len(s)\n",
    "\n",
    "        while j < s_length:\n",
    "            w = s[j]\n",
    "            if w in p.next:\n",
    "                p = p.next[w]\n",
    "                if p.word:\n",
    "                    if tmp_word_table[p.word] > 0:\n",
    "                        tmp_word_table[p.word] -= 1\n",
    "                        word_count += word_len\n",
    "                        if word_count == word_len*words_len:\n",
    "                            res.append(i)\n",
    "                            tmp_word_table = word_table.copy()\n",
    "                            word_count = 0\n",
    "                            i += word_len - 1 or 1\n",
    "                            j = i - 1\n",
    "                    else:\n",
    "                        tmp_word_table = word_table.copy()\n",
    "                        word_count = 0\n",
    "                        i += 1\n",
    "                        j = i - 1\n",
    "\n",
    "                    p = root\n",
    "                j += 1\n",
    "            else:\n",
    "                if word_count > 0:\n",
    "                    word_count = 0\n",
    "                    tmp_word_table = word_table.copy()\n",
    "                p = root\n",
    "                i += 1\n",
    "                j = i\n",
    "\n",
    "        return res\n",
    "    \n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.w = None\n",
    "        self.next = {}\n",
    "        self.word = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: 'str', words: 'List[str]') -> 'List[int]':\n",
    "        num = len(words)\n",
    "        if num == 0:\n",
    "            return []\n",
    "        word_len = len(words[0])\n",
    "        window_size = num * word_len\n",
    "        d = {}\n",
    "        str_len = len(s)\n",
    "        for i in range(num):\n",
    "            if words[i] in d:\n",
    "                d[words[i]] += 1\n",
    "            else:\n",
    "                d[words[i]] = 1\n",
    "        results = []\n",
    "        for start in range(word_len):\n",
    "            left = start\n",
    "            j = start\n",
    "            count = 0\n",
    "            subd = {}\n",
    "            while j < str_len - word_len + 1:\n",
    "                subword = s[j: j + word_len]\n",
    "                if subword in d:\n",
    "                    if subword in subd:\n",
    "                        subd[subword] += 1\n",
    "                    else:\n",
    "                        subd[subword] = 1\n",
    "                    count += 1\n",
    "                    while subd[subword] > d[subword]:\n",
    "                        subd[s[left: left + word_len]] -= 1\n",
    "                        left += word_len\n",
    "                        count -= 1\n",
    "                    if count == num:\n",
    "                        results.append(left)\n",
    "                else:\n",
    "                    left = j + word_len\n",
    "                    subd = {}\n",
    "                    count = 0\n",
    "                j += word_len\n",
    "        return results\n",
    "      \n",
    "                    \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        \n",
    "        if len(s) == 0:\n",
    "            return []\n",
    "        if len(words) == 0:\n",
    "            return []\n",
    "\n",
    "        ret_list = []\n",
    "        from collections import Counter\n",
    "        words_cnt = Counter(words)\n",
    "\n",
    "        # print(words_cnt)\n",
    "\n",
    "        length = len(words[0])\n",
    "        total_length = len(words) * length\n",
    "        \n",
    "        i = 0\n",
    "\n",
    "        while i + total_length <= len(s):\n",
    "\n",
    "            inner_words = []\n",
    "            for j in range(len(words)):\n",
    "                inner_words.append(s[i+j*length:i+(j+1)*length])\n",
    "            inner_words_cnt = Counter(inner_words)\n",
    "\n",
    "            if words_cnt == inner_words_cnt:\n",
    "                ret_list.append(i)\n",
    "            i += 1\n",
    "        \n",
    "        return ret_list\n",
    "\n",
    "\n",
    "\n",
    "    def get_result(self, s, words):\n",
    "        if len(s) == 0:\n",
    "            return []\n",
    "        if len(words) == 0:\n",
    "            return []\n",
    "\n",
    "        locs = []\n",
    "        length = len(words) * len(words[0])\n",
    "\n",
    "        # words_uniq = list(set(words))\n",
    "        for word in words:\n",
    "            state = self.kmp_state(word)\n",
    "            loc = self.kmp(s, word, state)\n",
    "            locs.append(loc)\n",
    "        \n",
    "        # print(locs)\n",
    "\n",
    "        ret_list = []\n",
    "        self.find(locs, [], ret_list, len(words[0]), 0)\n",
    "        return ret_list\n",
    "\n",
    "\n",
    "    def find(self, locs, loc_list, ret_list, single_length, d):\n",
    "        if d >= len(locs):\n",
    "            loc_list.sort()\n",
    "            # print(loc_list)\n",
    "            for i in range(1, len(loc_list)):\n",
    "                if (loc_list[i] - loc_list[i-1]) != single_length:\n",
    "                    return \n",
    "            if not loc_list[0] in ret_list:\n",
    "                ret_list.append(loc_list[0])\n",
    "            return \n",
    "\n",
    "        cur_loc = locs[d]\n",
    "        # print(\"cur_loc = {}\".format(cur_loc))\n",
    "        for loc in cur_loc:\n",
    "            # print(\"loc = {}\".format(loc))\n",
    "            self.find(locs, loc_list + [loc], ret_list, single_length, d+1)\n",
    "\n",
    "\n",
    "    \n",
    "    def kmp(self, txt, pat, state):\n",
    "        \n",
    "        loc = []\n",
    "\n",
    "        start = 0\n",
    "\n",
    "        while start < len(txt):\n",
    "            j = 0\n",
    "            for i in range(start, len(txt)):\n",
    "                c = txt[i]\n",
    "                if c in state[j].keys():\n",
    "                    j = state[j][c]\n",
    "                else:\n",
    "                    j = 0\n",
    "                if j == len(pat):\n",
    "                    start = i-len(pat)+1\n",
    "                    loc.append(start)\n",
    "                    break\n",
    "            start += 1\n",
    "        return loc\n",
    "\n",
    "    def kmp_state(self, pat):\n",
    "\n",
    "        state = [{}]\n",
    "        pat_char = list(set(pat))\n",
    "        for c in pat_char:\n",
    "            state[0][c] = 0\n",
    "        state[0][pat[0]] = 1\n",
    "        x = 0\n",
    "        for i in range(1, len(pat)):\n",
    "            c = pat[i]\n",
    "            state.append({})\n",
    "            for t in pat_char:\n",
    "                state[i][t] = state[x][t]\n",
    "            state[i][c] = i+1\n",
    "            x = state[x][c]\n",
    "        \n",
    "        return state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import Counter \n",
    "        if not s or not words:\n",
    "            return []\n",
    "        n,m=len(words),len(words[0])\n",
    "        k=n*m\n",
    "        d=sorted(words)\n",
    "        res=[]\n",
    "        for i in range(len(s)-k+1):\n",
    "            temp=[s[j*m+i:(j+1)*m+i] for j in range(n)]\n",
    "            if sorted(temp)==d:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        if len(words)==0:\n",
    "            return []\n",
    "        l,w=len(words),len(words[0])\n",
    "        words_len=l*w\n",
    "        c=Counter(words)\n",
    "        left=0\n",
    "        res=[]\n",
    "        while left<=len(s)-words_len:\n",
    "            w_list=[s[i:i+w] for i in range(left,left+words_len,w)]\n",
    "            if Counter(w_list)==c:\n",
    "                \n",
    "                res.append(left)\n",
    "            \n",
    "            left+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        if not s or not words:\n",
    "            return []       \n",
    "        s_n = len(s)\n",
    "        w_num = len(words)\n",
    "        w_len = len(words[0])\n",
    "        w_all_len = w_num * w_len\n",
    "        hash_map = Counter(words)\n",
    "        res = []\n",
    "        for i in range(s_n - w_len +1):\n",
    "            c_temp=s[i:i+w_all_len]\n",
    "            temp = []\n",
    "            for j in range(0,w_all_len,w_len):\n",
    "                temp.append(c_temp[j : j+w_len])\n",
    "            if Counter(temp)==hash_map:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "#         from collections import Counter\n",
    "#         if not s or not words:return []\n",
    "#         one_word = len(words[0])\n",
    "#         all_len = len(words) * one_word\n",
    "#         n = len(s)\n",
    "#         words = Counter(words)\n",
    "#         res = []\n",
    "#         for i in range(0, n - all_len + 1):\n",
    "#             tmp = s[i:i+all_len]\n",
    "#             c_tmp = []\n",
    "#             for j in range(0, all_len, one_word):\n",
    "#                 c_tmp.append(tmp[j:j+one_word])\n",
    "#             if Counter(c_tmp) == words:\n",
    "#                 res.append(i)\n",
    "#         return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter,defaultdict\n",
    "class Solution:\n",
    "    def is_same(self,c1,c2):\n",
    "        for k,v in c1.items():\n",
    "            if c2[k]!=v:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def slide_win(self,s,start,counter,L,l):\n",
    "        i,j=start,start+L\n",
    "        temp_counter=defaultdict(int)\n",
    "        for k in range(i,j,l):\n",
    "            temp_counter[s[k:k+l]]+=1\n",
    "        ans=[]\n",
    "\n",
    "        if self.is_same(counter,temp_counter):\n",
    "            ans.append(i)\n",
    "        \n",
    "        while j+l<=len(s):\n",
    "            temp_counter[s[j:j+l]]+=1\n",
    "            temp_counter[s[i:i+l]]-=1\n",
    "\n",
    "            i,j=i+l,j+l\n",
    "\n",
    "            if self.is_same(counter,temp_counter):\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        if not words or not s:\n",
    "            return []\n",
    "        \n",
    "        l=len(words[0])\n",
    "        L=l*len(words)\n",
    "\n",
    "        if len(s)<L:\n",
    "            return []\n",
    "\n",
    "        counter=Counter(words)\n",
    "        \n",
    "        ans=[]\n",
    "        for start in range(l):\n",
    "            ans+=self.slide_win(s,start,counter,L,l)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        word_list = []\n",
    "        for word in words:\n",
    "            word_list += word\n",
    "        res = []\n",
    "        l = len(s)\n",
    "        n = len(word_list)\n",
    "        m = int(n/len(words))\n",
    "        for i in range(l - n + 1):\n",
    "            str = s[i:i + n]\n",
    "            j = 0\n",
    "            while j <= len(str) - m + 1:\n",
    "                words_tmp = words.copy()\n",
    "                str_tmp = str[j:j + m]\n",
    "                while str_tmp in words_tmp:\n",
    "                    index = words_tmp.index(str_tmp)\n",
    "                    tmp = str.replace(words_tmp[index], '', 1)\n",
    "                    str = tmp\n",
    "                    words_tmp.pop(index)\n",
    "                    j += m\n",
    "                    str_tmp = str[0:m]\n",
    "                if len(str) == 0 and len(words_tmp) == 0:\n",
    "                    res.append(i)\n",
    "                j += m\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        wnum = len(words)\n",
    "        wlen = len(words[0])\n",
    "\n",
    "        res=[]\n",
    "        for i in range(0,len(s) - wlen*wnum + 1):\n",
    "            if s[i:i+wlen] in words:\n",
    "                tempwords = words.copy()\n",
    "                for j in range(wnum):\n",
    "                    if s[i+j*wlen:i+(j+1)*wlen] in tempwords:\n",
    "                        tempwords.remove(s[i+j*wlen:i+(j+1)*wlen])\n",
    "                    else:\n",
    "                        break\n",
    "                if len(tempwords) == 0:\n",
    "                    res.append(i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        myD = dict()\n",
    "        for word in words:\n",
    "            if word in myD:\n",
    "                myD[word] += 1\n",
    "            else:\n",
    "                myD[word] = 1\n",
    "        \n",
    "        w = len(words[0])\n",
    "        n = len(words)\n",
    "        l = w*n\n",
    "        ans = []\n",
    "        for i in range(len(s)-l+1):\n",
    "            myD_copy = dict()\n",
    "            tmp = s[i:i+l]\n",
    "            flag = 1\n",
    "            for j in range(n):\n",
    "                wd = s[i+w*j:i+w*(j+1)]\n",
    "                if wd in myD:\n",
    "                    if wd in myD_copy:\n",
    "                        myD_copy[wd] += 1\n",
    "                    else:\n",
    "                        myD_copy[wd] = 1\n",
    "                    if myD_copy[wd]>myD[wd]:\n",
    "                        flag = 0\n",
    "                        break\n",
    "                else:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        l=len(words[0])\n",
    "        lwords=len(words)\n",
    "        res=[]\n",
    "        queue=[]\n",
    "        qwords=[]\n",
    "        for j in range(l):\n",
    "            i=j\n",
    "            while i<len(s):\n",
    "                cur=s[i:i+l]\n",
    "                if cur in words:\n",
    "                    queue.append(i)\n",
    "                    qwords.append(cur)\n",
    "                    words.remove(cur)\n",
    "                    i+=l\n",
    "                    if not words:\n",
    "                        ans=queue.pop(0)\n",
    "                        if ans<=len(s)-l*lwords:res.append(ans)\n",
    "                        words.append(qwords.pop(0))\n",
    "                else:\n",
    "                    if queue:\n",
    "                        queue.pop(0)\n",
    "                        words.append(qwords.pop(0))\n",
    "                    else:\n",
    "                        i+=l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        res=[]\n",
    "        if not words:return res\n",
    "        \n",
    "        n=len(s)\n",
    "        m=len(words)\n",
    "        w=len(words[0])\n",
    "        tot=collections.defaultdict(int)\n",
    "        for i in words:\n",
    "            tot[i]+=1\n",
    "\n",
    "        for i in range(w):\n",
    "            cnt=0\n",
    "            wd=collections.defaultdict(int)\n",
    "            j=i\n",
    "            while j+w<=n:\n",
    "                if j>=i+m*w:\n",
    "                    word=s[j-m*w:j-(m-1)*w]\n",
    "                    wd[word]-=1\n",
    "                    if wd[word]<tot[word]:\n",
    "                        cnt-=1\n",
    "                word=s[j:j+w]\n",
    "                wd[word]+=1\n",
    "                if wd[word]<=tot[word]:\n",
    "                    cnt+=1\n",
    "                if cnt==m:\n",
    "                    res.append(j-(m-1)*w)\n",
    "                j+=w\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        res=[]\n",
    "        if not words:return res\n",
    "        \n",
    "        n=len(s)\n",
    "        m=len(words)\n",
    "        w=len(words[0])\n",
    "        tot=collections.defaultdict(int)\n",
    "        for i in words:\n",
    "            tot[i]+=1\n",
    "\n",
    "        for l in range(w):\n",
    "            cnt=0\n",
    "            wd=collections.defaultdict(int)\n",
    "            r=l\n",
    "            while r+w<=n:\n",
    "                #维护窗口大小，把左边往前缩紧一个（因为r也是每次遍历只加入一个）\n",
    "                if r>=l+m*w:\n",
    "                    word=s[r-m*w:r-(m-1)*w]\n",
    "                    wd[word]-=1\n",
    "                    if wd[word]<tot[word]:\n",
    "                        cnt-=1\n",
    "                #加入当前处理的右指针指向的即将加入的单词\n",
    "                word=s[r:r+w]\n",
    "                wd[word]+=1\n",
    "                if wd[word]<=tot[word]:\n",
    "                    cnt+=1\n",
    "                if cnt==m:\n",
    "                    res.append(r-(m-1)*w)\n",
    "                r+=w\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        main_dict = self.createDict(words)\n",
    "        num_list = []\n",
    "        word_map = {}\n",
    "        word_max_map = {}\n",
    "        for word in words:\n",
    "            if word in word_max_map:\n",
    "                word_max_map[word] += 1\n",
    "            else:\n",
    "                word_max_map[word] = 0\n",
    "        for word in words:\n",
    "            word_map[word] = 0\n",
    "        word_count = 0\n",
    "        first_i = 0\n",
    "        first_last_i = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            matched, last_i, this_s = self.match(s, i, main_dict)\n",
    "            if matched and word_map[this_s] <= word_max_map[this_s]:\n",
    "                # print(i)\n",
    "                word_map[this_s] += 1\n",
    "                word_count += 1\n",
    "                \n",
    "                if word_count == 1:\n",
    "                    first_i = i\n",
    "                    first_last_i = last_i\n",
    "\n",
    "                if word_count == len(words):\n",
    "                    # print(word_count)\n",
    "                    word_count = 0\n",
    "                    for word in words:\n",
    "                        word_map[word] = 0\n",
    "\n",
    "                    num_list.append(first_i)\n",
    "                    i = first_i + 1\n",
    "                else:\n",
    "                    i = last_i\n",
    "\n",
    "            else:\n",
    "                if word_count > 0:\n",
    "                    for word in words:\n",
    "                        word_map[word] = 0\n",
    "                    word_count = 0\n",
    "                    i = first_i + 1\n",
    "                else:\n",
    "                    i += 1\n",
    "\n",
    "        return num_list\n",
    "    \n",
    "    def match(self, s, i, node):\n",
    "        if len(node) == 0:\n",
    "            return True, i, ''\n",
    "        if i == len(s):\n",
    "            return False, -1, ''\n",
    "        if s[i] in node:\n",
    "            matched, last_i, acc_s = self.match(s, i+1, node[s[i]])\n",
    "            if matched:\n",
    "                return True, last_i, s[i] + acc_s\n",
    "\n",
    "        return False, -1, ''\n",
    "\n",
    "    def createDict(self, words: List[str]):\n",
    "        main = {}\n",
    "        for word in words:\n",
    "            node = main\n",
    "            for c in word:\n",
    "                if c not in node:\n",
    "                    node[c] = {}\n",
    "                node = node[c]\n",
    "\n",
    "        return main\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        if len(words) == 0 or len(s) == 0:\n",
    "            return []\n",
    "        \n",
    "        from collections import Counter\n",
    "        diction, length, answer = Counter(words), len(words[0]), []\n",
    "        for i in range(len(s)+1-len(words)*length):\n",
    "            dic = [s[i+j*length:i+(j+1)*length] for j in range(len(words))]\n",
    "            if Counter(dic) == diction:\n",
    "                answer.append(i)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        wordsdict={}\n",
    "        wordsdict1={}\n",
    "        indexlist=[]        \n",
    "        for iword in words:\n",
    "            wordsdict[iword]=wordsdict.get(iword,0)+1            \n",
    "        wordl=len(words[0])\n",
    "        numm=len(words)\n",
    "\n",
    "        slen=len(s)\n",
    "        for ii in range(wordl):\n",
    "            wordsdict1.clear()\n",
    "            left=ii\n",
    "            right=ii+wordl*numm\n",
    "            for iz in range(numm):\n",
    "                sstr=s[iz*wordl+ii:(iz+1)*wordl+ii]\n",
    "                wordsdict1[sstr]=wordsdict1.get(sstr,0)+1     \n",
    "            if wordsdict==wordsdict1:\n",
    "                indexlist.append(left)\n",
    "            while right<slen:            \n",
    "                right+=wordl\n",
    "                left+=wordl\n",
    "                wordsdict1[s[right-wordl:right]]=wordsdict1.get(s[right-wordl:right],0)+1                    \n",
    "                wordsdict1[s[left-wordl:left]]-=1\n",
    "                if wordsdict1[s[left-wordl:left]]==0:\n",
    "                    wordsdict1.pop(s[left-wordl:left])\n",
    "                if wordsdict==wordsdict1:\n",
    "                    indexlist.append(left)\n",
    "\n",
    "        return indexlist\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        slen = len(s)\n",
    "        wordlen = len(words[0])\n",
    "        listlen = len(words)\n",
    "\n",
    "        count = collections.Counter(words)\n",
    "\n",
    "        res = []\n",
    "        for i in range(slen):\n",
    "            diff = collections.Counter()\n",
    "            if i + wordlen * listlen > slen:\n",
    "                break\n",
    "            else:\n",
    "                for j in range(i, i + wordlen * listlen, wordlen):\n",
    "                    newword = s[j:j + wordlen]\n",
    "                    if newword not in count.keys():\n",
    "                        break\n",
    "                    diff[newword] += 1\n",
    "                if diff == count:\n",
    "                    res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        if not words:\n",
    "            return []\n",
    "        w_len, s_len = len(words[0]), len(s)\n",
    "        t_len = w_len * len(words)  # 子串的长度\n",
    "\n",
    "        word_dict = {}  # words的哈希表\n",
    "        for word in words:\n",
    "            word_dict[word] = word_dict.get(word, 0) + 1\n",
    "\n",
    "        ans = []\n",
    "        for offset in range(w_len):\n",
    "            lo, lo_max = offset, s_len - t_len\n",
    "            while lo <= lo_max:\n",
    "                tmp_dict = word_dict.copy()\n",
    "                match = True\n",
    "                for hi in range(lo + t_len, lo, -w_len):    # 从尾到头搜索单词\n",
    "                    word = s[hi - w_len: hi]\n",
    "                    if word not in tmp_dict or tmp_dict.get(word, 0) == 0:\n",
    "                        match = False\n",
    "                        break   # 当前单词不符合要求 直接停止这个子串的搜索\n",
    "                    tmp_dict[word] -= 1\n",
    "                if match:\n",
    "                    ans.append(lo)\n",
    "                lo = hi     # 对lo直接赋值 这就是相比法二优化的地方\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        if not words:\n",
    "            return []\n",
    "        w_len, s_len = len(words[0]), len(s)\n",
    "        t_len = w_len * len(words)  # 子串的长度\n",
    "\n",
    "        word_dict = {}  # words的哈希表\n",
    "        for word in words:\n",
    "            word_dict[word] = word_dict.get(word, 0) + 1\n",
    "\n",
    "        ans = []\n",
    "        for offset in range(w_len):\n",
    "            lo, lo_max = offset, s_len - t_len\n",
    "            while lo <= lo_max:\n",
    "                tmp_dict = word_dict.copy()\n",
    "                match = True\n",
    "                for hi in range(lo + t_len, lo, -w_len):    # 从尾到头搜索单词\n",
    "                    word = s[hi - w_len: hi]\n",
    "                    if word not in tmp_dict or tmp_dict.get(word, 0) == 0:\n",
    "                        match = False\n",
    "                        break   # 当前单词不符合要求 直接停止这个子串的搜索\n",
    "                    tmp_dict[word] -= 1\n",
    "                if match:\n",
    "                    ans.append(lo)\n",
    "                lo = hi     # 对lo直接赋值 这就是相比法二优化的地方\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        numword = len(words)\n",
    "        unitlen = len(words[0])\n",
    "        unique = list(set(words))\n",
    "        uniqcnt = [0 for x in unique]\n",
    "        for wd in words:\n",
    "            uniqcnt[unique.index(wd)] += 1\n",
    "        catch = []\n",
    "        starts = [-1 for i in range(len(s))]\n",
    "        for pos, char in enumerate(s):\n",
    "            for j in range(len(catch)):\n",
    "                iwd, ichar = catch[j]\n",
    "                if char == unique[iwd][ichar]:\n",
    "                    catch[j][1] += 1\n",
    "                else:\n",
    "                    catch[j][1] = -1\n",
    "            for j in range(len(catch)-1, -1, -1):\n",
    "                if catch[j][1] == unitlen:\n",
    "                    starts[pos-unitlen+1] = catch[j][0]\n",
    "                    catch.pop(j)\n",
    "                elif catch[j][1] == -1:\n",
    "                    catch.pop(j)\n",
    "            for i in range(len(unique)):\n",
    "                if char == unique[i][0]:\n",
    "                    if unitlen == 1:\n",
    "                        starts[pos] = i\n",
    "                    else:\n",
    "                        catch.append([i, 1])\n",
    "        merge = []\n",
    "        ans = []\n",
    "        tail = len(s) - unitlen * numword\n",
    "        for pos in range(len(s)):\n",
    "            for i in range(len(merge)):\n",
    "                if pos != merge[i][0]:\n",
    "                    continue\n",
    "                if starts[pos] != -1:\n",
    "                    iu = starts[pos]\n",
    "                    merge[i][1][iu] += 1\n",
    "                    merge[i][0] += unitlen\n",
    "                    if merge[i][1] == uniqcnt:\n",
    "                        ans.append(merge[i][0]-numword*unitlen)\n",
    "                        merge[i][0] = -1\n",
    "                    if merge[i][1][iu] > uniqcnt[iu]:\n",
    "                        merge[i][0] = -1\n",
    "                else:\n",
    "                    merge[i][0] = -1\n",
    "            for i in range(len(merge)-1, -1, -1):\n",
    "                if merge[i][0] <= pos:\n",
    "                    merge.pop(i)\n",
    "            if pos<=tail and starts[pos] != -1:\n",
    "                if numword == 1:\n",
    "                    ans.append(pos)\n",
    "                else:\n",
    "                    merge.append([pos+unitlen, [0 for u in unique]])\n",
    "                    merge[-1][1][starts[pos]] = 1\n",
    "            if pos>tail and len(merge)==0:\n",
    "                break\n",
    "        return ans\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        result=[]\n",
    "        size=len(words)*len(words[0])\n",
    "        cnt=Counter(words)\n",
    "        for i in range(0,len(s)-size+1):\n",
    "            window=s[i:i+size]\n",
    "            ls=[]\n",
    "            for j in range(len(words)):\n",
    "                ls.append(window[j*len(words[0]):(j+1)*len(words[0])])\n",
    "            if Counter(ls)==cnt:\n",
    "                result.append(i)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        total_len = len(words) * len(words[0])\n",
    "        d={}\n",
    "        for i in words:\n",
    "            d[i] = d.get(i,0)+1\n",
    "        res = []\n",
    "        x={}\n",
    "        for i in range(len(s)-total_len+1):\n",
    "            search_str = s[i:i+total_len]\n",
    "            x = d.copy()\n",
    "\n",
    "            for j in range(0,len(search_str),len(words[0])):\n",
    "                if search_str[j:j+len(words[0])] in d and x[search_str[j:j+len(words[0])]]!=0:\n",
    "                    x[search_str[j:j+len(words[0])]] -= 1\n",
    "                else:\n",
    "                    break   \n",
    "            if sum(x.values()) == 0:\n",
    "                res.append(i)\n",
    "        return res\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        str_len = len(s)\n",
    "        one_word = len(words[0])\n",
    "        word_num = len(words)\n",
    "        ans=[]\n",
    "        if not s or not words or str_len < one_word*word_num: return []\n",
    "        for i in range(0,str_len-one_word*word_num+1,1):\n",
    "            words_cmp=[]\n",
    "            for j in range(word_num):\n",
    "                words_cmp.append(s[i+j*one_word:i+j*one_word+one_word:1])\n",
    "            if Counter(words_cmp) == Counter(words):\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "        cnt, l = len(words), len(words[0])\n",
    "        i, j = 0, cnt * l - 1\n",
    "        ans = []\n",
    "        check = collections.Counter(words)\n",
    "        while j < len(s):\n",
    "            ss = s[i : j + 1]\n",
    "            tmp = []\n",
    "            for k in range(0, len(ss), l):\n",
    "                tmp.append(ss[k: k + l])\n",
    "            if collections.Counter(tmp) == check:\n",
    "                ans.append(i)\n",
    "            i += 1\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSubstring(self, s: str, words: List[str]) -> List[int]:\n",
    "\n",
    "        n, m, ls = len(words[0]), len(words), len(s)\n",
    "\n",
    "        if n * m > ls:\n",
    "            return []\n",
    "\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            word_dict = {}\n",
    "            cnt = 0\n",
    "            for word in words:\n",
    "                if word_dict.get(word) is None:\n",
    "                    word_dict[word] = 0\n",
    "                word_dict[word] += 1\n",
    "                cnt += 1\n",
    "            \n",
    "            for j in range(m):\n",
    "                if j * n + i + n - 1 >= ls:\n",
    "                    break\n",
    "                word = s[j * n + i:j * n + i + n]\n",
    "                if word_dict.get(word) is not None:\n",
    "                    word_dict[word] -= 1\n",
    "                    if word_dict[word] >= 0:\n",
    "                        cnt -= 1\n",
    "\n",
    "            if cnt == 0:\n",
    "                res.append(i)\n",
    "\n",
    "            for j in range(i, ls - m * n + 1, n):\n",
    "                word = s[j:j+n]\n",
    "                if word_dict.get(word) is not None:\n",
    "                    word_dict[word] += 1\n",
    "                    if word_dict[word] > 0:\n",
    "                        cnt += 1\n",
    "\n",
    "                word = s[j+m*n:j+m*n+n]\n",
    "                if word_dict.get(word) is not None:\n",
    "                    word_dict[word] -= 1\n",
    "                    if word_dict[word] >= 0:\n",
    "                        cnt -= 1\n",
    "\n",
    "                if cnt == 0:\n",
    "                    res.append(j+n)\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
